package cn.lbd.arithmetic.sort;

import org.junit.Test;

import java.util.Arrays;

//堆排序
public class HeapSort {

    /**
     * @param array
     */
    public static void sort(int[] array) {
        int temp = 0;
        //从最后一个非叶子结点开始调整数组
        for (int i = (array.length - 1) / 2; i >= 0; i--) {
            adjustHeap(array, i, array.length);
        }
        //将堆顶和末尾交换，并调整交换后
        //被破坏的堆结构
        for (int j = array.length - 1; j > 0; j--) {
            temp = array[0];
            array[0] = array[j];
            array[j] = temp;
            adjustHeap(array, 0, j);
        }
    }

    /**
     * 调整堆
     *
     * @param arr    待调整的二叉树（数组）
     * @param i      最后一个非叶子结点的索引
     * @param length 数组长度
     */

    public static void adjustHeap(int arr[], int i, int length) {
        int temp = arr[i];
        //k每次，k每次迭代更新为他的下一左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //选择左右节点更大的一个
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            //这里的k已经选择好了
            if (arr[k] > temp) {
                arr[i] = arr[k];
                //当前节点向子节点迭代
                i = k;
            } else {//因为调整顺序从下到上，从左到右，所以每次的子树都是排好的
                break;
            }
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] array = {4, 6, 8, 5, 9};
        sort(array);
        System.out.println(Arrays.toString(array));
    }


    //8000000数据2.143
    @Test
    public void batchTest() {
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }

        long start = System.currentTimeMillis();

        sort(arr);

        long end = System.currentTimeMillis();

        System.out.println((double) (end - start) / 1000);
    }


}
